package com.my.algorithmlearning.leetcode;

import com.my.algorithmlearning.entity.TreeNode;

/**
 * @ClassName Medium_236_LowestCommonAncestor_DFS
 * @Description https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/solutions/625063/236-er-cha-shu-de-zui-jin-gong-gong-zu-x-tl5b/
 * @Author wanghaiwei
 * @Date 2023/6/26 11:00
 */
public class Medium_236_LowestCommonAncestor_DFS {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == p || root == q || root == null) {
            return root;
        }
        TreeNode leftNode = lowestCommonAncestor(root.left, p, q);
        TreeNode rightNode = lowestCommonAncestor(root.right, p, q);
        if (leftNode != null && rightNode != null) {
            return root;
        }else {
            return leftNode == null ? rightNode : leftNode;
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        TreeNode leftNode = new TreeNode(5);
        TreeNode rightNode = new TreeNode(1);
        TreeNode leftLeftNode = new TreeNode(6);
        TreeNode leftRightNode = new TreeNode(2);
        TreeNode rightLeftNode = new TreeNode(0);
        TreeNode rightRightNode = new TreeNode(8);
        TreeNode leftRightLeftNode = new TreeNode(7);
        TreeNode leftRightRightNode = new TreeNode(4);
        root.left = leftNode;
        root.right = rightNode;
        leftNode.left = leftLeftNode;
        leftNode.right = leftRightNode;
        rightNode.left = rightLeftNode;
        rightNode.right = rightRightNode;
        leftRightNode.left = leftRightLeftNode;
        leftRightNode.right = leftRightRightNode;
        Medium_236_LowestCommonAncestor_DFS lowestCommonAncestor = new Medium_236_LowestCommonAncestor_DFS();
        TreeNode treeNode = lowestCommonAncestor.lowestCommonAncestor(root, leftNode, rightNode);
        System.out.println(treeNode.val);
    }
}
